『BZOJ 4520』[CQOI2016]K远点对

Problem

Description
已知平面内 $N$ 个点的坐标，求欧氏距离下的第 $K$ 远点对。

Input
输入文件第一行为用空格隔开的两个整数$N, K$。接下来$N$ 行，每行两个整数 $X,Y$，表示一个点
的坐标。$1 \leq N \leq 100000， 1 \leq K \leq 100， K \leq \dfrac{N (N−1)}{2} ， 0 \leq X, Y < 2^31$。

Output
输出文件第一行为一个整数，表示第 $K$远点对的距离的平方（一定是个整数）。

Sample Input
10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1
Sample Output
9

Solution

这题是KDTree模板题啊Orzzz
然额本蒟蒻打了好久才调出来
原因：

简直了。。
附上蒟蒻代码：（太懒没时间打注释）
跑的实在是巨慢：

顺便说一句：那个MAX和MIN记录的是当前矩阵区域内最大的横纵坐标值

复制

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <cmath>
#define MAXN 100011
int N, K, nowD, root, ql, qr; 
using namespace std;
struct node
{
	long long dis;
	inline bool operator < (const node &a) const
	{
		return a.dis < dis;
	}
};
typedef struct KDTree
{
	int d[2], Min[2], Max[2], l, r;
} KDT;
KDT Tree[MAXN];
priority_queue <node> Q;
inline long long sqr(long long a)
{
	return a * a;
}
inline void MAX(KDT &a, KDT b, int type)
{
	a.Max[type] = max(a.Max[type], b.Max[type]);
}
inline void MIN(KDT &a, KDT b, int type)
{
	a.Min[type] = min(a.Min[type], b.Min[type]);
}
inline long long GetDis(int x, int y)
{
	return sqr(Tree[x].d[0] - Tree[y].d[0]) + sqr(Tree[y].d[1] - Tree[x].d[1]);
}
inline bool cmp(KDT a, KDT b)
{
	if (a.d[nowD] == b.d[nowD])
	{
		return a.d[nowD ^ 1] < b.d[nowD ^ 1];
	}
	else
	return a.d[nowD] < b.d[nowD];
}
inline void Update(int x)
{
	if (Tree[x].l) for (register int i = 0; i < 2; ++i) MAX(Tree[x], Tree[Tree[x].l], i), MIN(Tree[x], Tree[Tree[x].l], i);
	if (Tree[x].r) for (register int i = 0; i < 2; ++i) MAX(Tree[x], Tree[Tree[x].r], i), MIN(Tree[x], Tree[Tree[x].r], i);
}
inline int Build(int l, int r, int D)
{
	nowD = D;
	int mid = (l + r) >> 1;
	nth_element(Tree + l + 1, Tree + mid + 1, Tree + r + 1, cmp);
	if (l < mid) Tree[mid].l = Build(l, mid - 1, D ^ 1);
	if (mid < r) Tree[mid].r = Build(mid + 1, r, D ^ 1);
	for (register int i = 0; i < 2; ++i)
		Tree[mid].Min[i] = Tree[mid].Max[i] = Tree[mid].d[i];
	Update(mid);
	return mid;
}
inline long long Adis(KDT A, KDT B)
{
	return max(sqr(A.d[0] - B.Min[0]), sqr(A.d[0] - B.Max[0])) + max(sqr(A.d[1] - B.Min[1]), sqr(A.d[1] - B.Max[1]));
}
inline void Query(int x)
{
	long long dl = 0, dr = 0;
	long long dis = GetDis(0, x);
	if (dis > Q.top().dis)
	{
		Q.pop();
		Q.push((node){ dis });
	}
	if (Tree[x].l) dl = Adis(Tree[0], Tree[Tree[x].l]);
	if (Tree[x].r) dr = Adis(Tree[0], Tree[Tree[x].r]);
	if (dl > dr)
	{
		if (dl > Q.top().dis) Query(Tree[x].l);
		if (dr > Q.top().dis) Query(Tree[x].r);
	}
	else
	{
		if (dr > Q.top().dis) Query(Tree[x].r);
		if (dl > Q.top().dis) Query(Tree[x].l);
	}
}
int main(int argc, char **argv)
{
	ios::sync_with_stdio(false); 
	cin >> N >> K;
	for (register int i = 1; i <= N; ++i)
	{
		cin >> Tree[i].d[0] >> Tree[i].d[1];
	}
	root = Build(1, N, 0);
	for (register int i = 1; i <= K * 2; ++i)
		Q.push((node) { 0 });
	for (register int i = 1; i <= N; ++i)
	{
		Tree[0].d[0] = Tree[i].d[0];
		Tree[0].d[1] = Tree[i].d[1];
		Query(root); 
	}
	cout << Q.top().dis << endl;
	return 0;
}